package com.tgy.recursion;

/**
 * @Author: tgy
 * @Date: 2020-10-29 10:30
 */
public class Fib {

    public long fib(int n) {

        if (n <= 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public long tailFib(int n) {

        if (n <= 2) {
            return 1;
        }

        long first = 1,second = 1;
        return tailFib(n,first,second);
    }

    private long tailFib(int n, long first,long second) {

        if (n == 2) {

            return second;
        }

        second = first + second;
        first  = second - first;
        return tailFib(n - 1,first,second);
    }

    public long fib01(int n) {

        if (n <= 2) {
            return 1;
        }

        long[] cache = new long[n + 1];

        cache[1] = cache[2] = 1;

       return cacheFib01(n,cache);
    }

    /**
     * 滚动数组
     * @return
     */
    public long fib02(int n) {

        if (n <= 2) {
            return 1;
        }

        long[] cache = new long[2];

        cache[0] = cache[1] = 1;

        for (int i = 3; i <= n; i++) {

            cache[i & 1] = cache[(i - 1) & 1] + cache[(i - 2) & 1];
        }

        return cache[n & 2];
    }

    public long fib03(int n) {

        if (n <= 2) {

            return 1;
        }

        int first  = 1, second=1;

        for (int i = 3; i <= n; i++) {

            second = first + second;
            first = second - first;
        }

        return second;
    }

    private long cacheFib01(int n, long[]cache) {


        if (cache[n] == 0) {

            // 缓存没有就创建，有就返回缓存的值
            cache[n] = cacheFib01(n-1,cache) + cacheFib01(n-2,cache);
        }

        return cache[n];
    }
}
